/**
 * 下一个排列
 *
 * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 *
 * 示例 2：
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 *
 * 示例 3：
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 */

import java.util.Arrays;

/**
 * 这题的思路就是找规律吧, 我发现, 现在毫无头绪的题目只要你把过程画出来, 分析分析这
 * 其中的规律, 只要你分析的思路是对的, 不管是暴力还是啥的, 只要你能写出来, 这个方法
 * 就可解, 其中如果有方法的时间复杂度是超了的, 我们可以先考虑使用我们学到的方法, 来
 * 优化这个时间复杂度要是还不行, 我们就要换个思路了
 * 这题就是找规律找的, 我们将 1 2 3 4 5 的列举出来
 * 1 2 3 4 5 -> 1 2 3 5 4 -> 1 2 4 3 5 -> 1 2 4 5 3
 * 1.我们不难发现, 每次我们在后面的数不是降序的时候只需要将他们的顺序交换一下就可以了
 * 这里为了顺利交换两个数, 我们是从后面开始遍历的
 * 2.要是后面已经是降序的了, 我们就需要将最后面一个最小的数和前面一个数交换位置了,
 * 因为这个数开头的已经列举完了, 后面就是在将后面的数排成从小到大的顺序(这里因为后面的数已经是降序的了)
 * 所以可以投机取巧一下, 两两交换他们的位置, 以达到升序的目的, 然后这里其实要注意下我们解决的是表面上的
 * 情况, 当我们遇到 5 4 7 5 3 2 -> 5 5 2 3 4 7 这个时候并不是和最后一个数交换, 反而是要先找到后面
 * 的数比他大的最小数, 还好后面是降序的. 我们只需要从后向前遍历, 第一个比他大的数就是我们要找的该交换位置
 * 的数了, 后面就是一样的步骤, 排成升序, 后面该处理啥就处理啥
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = new int[]{1, 4, 3, 2};
        test.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {

        // 数组长度
        int n = nums.length;

        // 这里我们特殊处理长度为 0 和 1, 就直接返回
        if (n == 0 || n == 1) {
            return;
        }

        // 如果长度为 2 的话, 交换这两个数就可以了
        if (n == 2) {
            if (nums[0] < nums[1]) {
                swap(nums, 0, 1);
            }
            return;
        }

        // 如果整个数组降序的话也是要特殊处理的, 就是返回整个正序数组
        if (isDesc(nums, 0, n - 1)) {
            sortNums(nums, 0, n - 1);
            return;
        }

        // 这里我们从后面两个数开始遍历, 要是降序就向前判断, 直到找到有不是降序的, 然后开始找需要替换
        // 的位置, 替换后将后面的数化成正序数就可以了
        for (int i = n - 2; i >= 0; i--) {

            // 判断 i ~ n - 1 是否为降序
            if (!isDesc(nums, i, n - 1)) {

                // 不是降序
                // 定义初始位置和需要交换的位置
                int left = i;

                // 查找需要交换的位置
                int right = findLowerNums0(nums, i, n - 1);

                // 交换两个数
                swap(nums, left, right);

                // 正排序后面的数
                sortNums(nums, left + 1, n - 1);
                return;
            }

            // 没找到就一直向后面遍历
        }
    }

    /**
     * 原地交换数组中的元素
     *
     * @param nums  数组
     * @param i     交换的第一个下标
     * @param j     交换的第二个下标
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 判断传入的位置是否为降序
     *
     * @param nums  数组
     * @param i     开始的位置
     * @param j     结束的位置
     * @return
     */
    private boolean isDesc (int[] nums, int i, int j) {
        int tmp = nums[i];
        for (int k = i; k <= j; k++) {
            if (tmp < nums[k]) {
                return false;
            }
            tmp = nums[k];
        }
        return true;
    }

    /**
     * 将数组传入的位置排为升序
     *
     * @param nums  数组
     * @param i     起始位置
     * @param j     结束位置
     */
    private void sortNums(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    /**
     * 找寻特定位置比给定数第一大的数(要是这些数中最小的)
     *
     * @param nums     数组
     * @param target   给定的数
     * @param n        数组末位置
     * @return
     */
    private int findLowerNums0(int[] nums, int target, int n) {
        for (int i = n; i >= 1; i--) {
            if (nums[i] > nums[target]) {
                return i;
            }
        }
        return 0;
    }
}